Two Stage Time Minimizing Transportation Problem with Restricted Flow
Prabhjot Kaur and Kalpana Dahiya*
UIET, Panjab University, Chandigarh-160014, India.
*Corresponding Author E-mail: prabh.g3@gmail.com, kalpanas@pu.ac.in
ABSTRACT:
In this paper, a two stage time minimizing transportation problem (TSTMTP) with restricted flow is considered, in which the total availability of a homogeneous product at various sources is more than the total minimum requirement of the same at destinations. In the current problem, transportation takes place in two stages such that a fixed flow F1(greater than or equal to the total minimum requirement at the destinations) is transported in the first stage and another fixed flow F2 is transported in the second stage so as to meet the exact total requirement of the destinations. Each time the transportation from sources to destination is done in parallel. The objective is to find that feasible solution of Stage-I corresponding to which the optimal feasible solution (OFS) of Stage-II is such that the sum of the shipment times in Stage-I and Stage-II is minimum. A polynomial time iterative algorithm is proposed to solve the current problem.
KEYWORDS: Time transportation problem, Combinatorial optimization, non-convex programming, Bottleneck linear programming, Flow constrained transportation problem.
INTRODUCTION:
In (1969), Hammer first discussed the time minimizing transportation problem. It is a special case of bottleneck linear programming problem, which deals with minimization of a concave bottleneck objective function or the maximization of a convex bottleneck objective function over a convex region. Garfinkel et al. (1971), Bhatia et al. (1977), Bansal et al. (1980), Issermann (1984), Arora and Puri (2001) and many other authors proposed various algorithms to solve time minimization transportation problem (TMTP). TMTPs with mixed constraints and flow constraints have been studied by Khanna et al. (1981, 1983). In TMTP, the transportation of goods from sources to destinations is done in parallel and the aim of this problem is to supply to the destinations with the required quantity within the shortest possible time. The mathematical structure proposed by Hammer for this problem is as follows:
4. Algorithm
Initial
Step: Obtain an OFS of the problem 
and note the Stage-I and Stage-II times as
say. If 
,
then stop and go to terminal step; else, go to General step.
General
Step: Let the pairs in hand be (
) for 
. Construct the problem 
and find its OFS. If this is not an M- feasible solution, then
stop and go to terminal step, otherwise read the time 
of Stage-I and 
of Stage-II. If 
, Stop and go to terminal step, else repeat the general step for
higher values of k.
Terminal
Step: Declare
as the optimal value of objective function of the problem (
).
5. Numerical Illustration
|
|
|
|
|
|
|
|
|
|
|
|
5 |
6 |
4 |
3 |
5 |
6 |
4 |
100 |
|
|
12 |
9 |
12 |
10 |
9 |
12 |
10 |
80 |
|
|
2 |
8 |
7 |
9 |
8 |
4 |
9 |
110 |
|
|
11 |
5 |
9 |
8 |
11 |
9 |
8 |
90 |
|
|
6 |
10 |
5 |
3 |
6 |
5 |
10 |
120 |
|
|
12 |
4 |
2 |
10 |
10 |
12 |
4 |
50 |
|
|
80 |
50 |
70 |
40 |
60 |
70 |
30 |
|
Consider
the following 
transportation problem given in Table-I. In this problem 
and 
and the amount to be sent in first stage is 
and in second stage is 
50. Here 
Table-1
Initial
Step: An (OBFS) of the problem 
gives 
and the corresponding 
So the current value of 
Since 
Go to general step of the algorithm.
General Step.
Iteration
1. Construct the problem 
it’s (OBFS) yields value 
and the corresponding
. The current value of 
is min (
) =14. As
, solve 
Iteration
2. 
Yields time 
Iteration3.
Yields time 
Since
stop and go to terminal step.
Terminal step.
The
optimal value of the objective function of the problem () is given by
An
Optimal feasible solution of the problem 
is shown in Table-2,
The entries in the upper right corner of each cell give the time of transportation. Note that the entries in boldface represent the
basic
cells. Feasible solution of Stage-I and Stage-II problems corresponding to the
(OFS) of the problem 
can be
read from Table2.
Table-2
|
5 |
6 |
4
|
3 |
5
|
6 |
4
|
3 |
M |
|
M |
9 |
M |
M |
9
|
M |
M |
9
|
M |
|
2
|
8 |
7 |
9 |
8 |
4 |
9 |
2 |
0
|
|
M |
5
|
9 |
8 |
M |
9 |
8 |
5
|
M |
|
6 |
M |
5 |
3
|
6 |
5
|
M |
3
|
M |
|
M |
4 |
2
|
M |
M |
M |
4 |
2 |
0
|
1.
As Stage-II time is strictly decreasing at each iteration and if 
and for some 
the maximum number of iterations required to solve the problem is 
where p is the total number of distinct time entries in the 
array. Hence the algorithm converges in a finite number of steps.
2. In
the problem (
) there is no bound on the capacity along any route, the problem
can be made more meaningful by imposing bounds on the capacity of each route.
3. Two stage time minimizing transportation problem with restricted flow discussed in this paper can be further explored in case of multi-stage transportation problem.